/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 第i个元素代表第i天的股票，求最大交易利润，允许最多交易两次
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class BestTimeBuyAndSellStockIII {

    public int maxProfit(int[] prices) {
        int result = 0;
        if (prices == null || prices.length == 0) {
            return result;
        }
        int len = prices.length;
        // 为截止当日的最大利润
        int[] curProfit = new int[len];
        // 当日以后交易的最大利润
        int[] futureProfit = new int[len];
        int low = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < len; i++) {
            low = Math.min(low, prices[i]);
            curProfit[i] = Math.max(curProfit[i - 1], prices[i] - low);
        }
        int high = prices[len - 1];
        // 计算该日以后交易的最大利润，合计之前利润，求得最大利润
        for (int i = len - 1; i >= 0; i--) {
            high = Math.max(high, prices[i]);
            if (i < len - 1) {
                futureProfit[i] = Math.max(futureProfit[i + 1], high - prices[i]);
            }
            maxProfit = Math.max(maxProfit, curProfit[i] + futureProfit[i]);
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {1, 2};
        BestTimeBuyAndSellStockIII sellStock = new BestTimeBuyAndSellStockIII();
        System.out.println(sellStock.maxProfit(prices));
    }
}
